package psn.zjk.career.interview.algorithm.tree;

/**
 * @author zhangjk
 * @CREATE_TIME 2021/2/18 14:46
 * 给你二叉搜索树的根节点 root ，该树中的！两个节点！被错误地交换。请在不改变其结构的情况下，恢复这棵树
 *
 * 思路：找到需要交换的两个点，点1是第一个逆序的点，点2是最后一个逆序点的后一个（逆序：前者大于后者）
 */
public class LeetCode99 {
    /**
     * 遍历的上一个节点
     */
    private TreeNode prev=new TreeNode(Integer.MIN_VALUE);
    /**
     * 第一个交换节点
     */
    private TreeNode swapNode2;
    /**
     * 第二个交换节点
     */
    private TreeNode swapNode1;


    public void recoverTree(TreeNode root) {
        traverse(root);
        int tmp = swapNode1.val;
        swapNode1.val = swapNode2.val;
        swapNode2.val = tmp;
    }

    public void traverse(TreeNode current) {
        //中序遍历
        //1.左
        if (current == null) return;
        traverse(current.left);
        //2.中：逻辑部分
        if (current.val < prev.val) {//逆序
            if (swapNode1 == null) {//第一个交换节点取较大值，大的放后面
                swapNode1 = prev;
            }
            swapNode2 = current;//第二个取较小值，小的放前面
        }
        prev = current;
        //3.右
        traverse(current.right);
    }

}